#include"Sort.h"
#include"Stack.h"
void swap(int* x, int* y)
{
	int t = *x;
	*x = *y;
	*y = t;
}
int _QuickSort(int* arr, int left, int right)
{
	int hole = left;
	int key = arr[hole];
	while (left < right)
	{
		while(left<right && arr[right] >= key)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;
}
int _QuickSort1(int* arr, int left, int right)
{
	int prev = left;
	int pcur = left+1;
	int key = left;
	while (pcur <= right)
	{
		if (arr[pcur] < arr[key] && ++prev != pcur)
		{
			swap(&arr[pcur], &arr[prev]);
		}
		++pcur;
	}
	swap(&arr[key], &arr[prev]);
	return prev;
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = _QuickSort1(arr, left, right);
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi+1,right);

}
